home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Libris Britannia 4
/
science library(b).zip
/
science library(b)
/
ELECTRON
/
0989.ZIP
/
ESPRESSO.ARC
/
ESPRESSO.DOC
< prev
next >
Wrap
Text File
|
1987-03-14
|
26KB
|
661 lines
EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((1111)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((1111))))
NNNNAAAAMMMMEEEE
espresso - Boolean Minimization
SSSSYYYYNNNNOOOOPPPPSSSSIIIISSSS
eeeesssspppprrrreeeessssssssoooo [_t_y_p_e] [_f_i_l_e] [_o_p_t_i_o_n_s]
DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
_E_s_p_r_e_s_s_o takes as input a two-level representation of a
two-valued (or a multiple-valued) Boolean function, and
produces a minimal equivalent representation. The
algorithms used are new and represent an advance in both
speed and optimality of solution in heuristic Boolean
minimization.
_E_s_p_r_e_s_s_o reads the _f_i_l_e provided (or standard input if no
files are specified), performs the minimization, and writes
the minimized result to standard output. _E_s_p_r_e_s_s_o
automatically verifies that the minimized function is
equivalent to the original function.
The default input and output file formats are compatible
with the Berkeley standard format for the physical
description of a PLA. The input format is described in
detail in espresso(5). Note that the input file is a
_l_o_g_i_c_a_l representation of a set of Boolean equations, and
hence the input format differs slightly from that described
in pla(5) (which provides for the _p_h_y_s_i_c_a_l representation of
a PLA). The input and output formats have been expanded to
allow for multiple-valued logic functions, and to allow for
the specification of the don't care set which will be used
in the minimization.
_T_y_p_e specifies the logical format for the function. The
allowed types are -f, -r, -fr, -fd, -dr, and -fdr which have
the same meanings assigned in espresso(5).
The command line options described below can be specified
anywhere on the command line and must be separated by
spaces:
----dddd Verbose detail describing the progress of the
minimization is written to standard output. Useful
only for those familiar with the algorithms used.
----ddddoooo [[[[ssss]]]] This option executes subprogram [s]. Some of the
more useful ones are:
cccchhhheeeecccckkkk - checks that the function is a partition of
the entire space (i.e., that the ON-set, OFF-set and
DC-set are pairwise disjoint, and that their union
is the Universe)
eeeecccchhhhoooo - implies "-out fdr" and echoes the function to
standard output. This can be used to compute the
Page 1 (printed 3/14/87)
EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((1111)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((1111))))
complement of a function.
ooooppppoooo - choose a good assignment of output function
phases, and minimize the function
qqqqmmmm - generate all prime implicants of a function,
compute the "reduced prime implicant table" and
perform a simple greedy covering of this table.
Will also provide a bound on the size of the minimum
solution if option -d is used.
ssssttttaaaattttssss - provide simple statistics on the size of the
function
The remaining subprograms (contain, compact, essen,
expand, intersect, irred, lexsort, mincov,
miniexpord, miniredord, pop, primes, reduce, sharp,
taut, union, unravel, verify + surely others by now)
are intended for those heavily into manipulating
Boolean functions.
----ffffaaaasssstttt Stop after the first EXPAND and IRREDUNDANT
operations (i.e., do not iterate over the solution).
----kkkkiiiissssssss Sets up a _k_i_s_s-style minimization problem.
----nnnneeeessssssss Essential primes will not be detected and removed
from the minimization.
----nnnniiiirrrrrrrr The final result will not necessarily be forced
irredundant.
----hhhheeeellllpppp Provides a quick summary of the available command
line options.
----oooouuuutttt [[[[ssss]]]]
Selects the output format. By default, only the
ON-set (i.e., type f) is output after the
minimization. [s] can be one of f, d, r, fd, dr,
fr, or fdr to select any combination of the ON-set
(f), the OFF-set (r) or the DC-set (d).
----ppppoooossss Swaps the ON-set and OFF-set of the function after
reading the function. (This can be used to minimize
the OFF-set of a function.)
----ssss Will provide a short summary of the execution of the
program including the initial cost of the function,
the final cost, and the computer resources used.
----tttt Will produce a trace showing the execution of the
program. After each main step of the algorithm, a
single line is printed which reports the processor
time used, and the current cost of the function.
----xxxx Suppress printing of the solution.
Page 2 (printed 3/14/87)
EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((1111)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((1111))))
DDDDIIIIAAAAGGGGNNNNOOOOSSSSTTTTIIIICCCCSSSS
_e_s_p_r_e_s_s_o will issue a warning message if a product term
spans more than one line. Usually this is an indication
that the number of inputs or outputs of the function is
specified incorrectly.
SSSSEEEEEEEE AAAALLLLSSSSOOOO
pla(5), espresso(5)
_L_o_g_i_c _M_i_n_i_m_i_z_a_t_i_o_n _A_l_g_o_r_i_t_h_m_s _f_o_r _V_L_S_I _S_y_n_t_h_e_s_i_s, R.
Brayton, G. Hachtel, C. McMullen, and A. Sangiovanni-
Vincentelli, Kluwer Academic Publishers, 1984.
AAAAUUUUTTTTHHHHOOOORRRR
Richard Rudell
BBBBUUUUGGGGSSSS
Always passes comments from the input file, and passes
unrecognized options straight from the input file to
standard output (sometimes this isn't what you want).
There are a lot of options, but the most typical use is the
following:
eqntott -r file.eqn | espresso >file.pla
The -R option of eqntott should not be used (it is much too
expensive).
Page 3 (printed 3/14/87)
EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555))))
NNNNAAAAMMMMEEEE
espresso -- input file format for espresso(1)
DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
_E_s_p_r_e_s_s_o accepts as input a two-level description of a
Boolean switching function. This is described as a
character matrix with keywords imbedded in the input to
specify the size of the matrix and the logical format of the
input function. Comments are allowed within the input by
placing a pound sign (#) as the first character on a line.
Comments and unrecognized keywords are passed directly from
the input file to standard output. Any white-space (blanks,
tabs, etc.), except when used as a delimiter in an imbedded
command, is ignored. It is generally assumed that the PLA
is specified such that each row of the PLA fits on a single
line in the input file.
KKKKEEEEYYYYWWWWOOOORRRRDDDDSSSS
The following keywords are recognized by _e_s_p_r_e_s_s_o. The list
shows the probable order of the keywords in a PLA
description. [d] denotes a decimal number and [s] denotes a
text string.
....iiii [[[[dddd]]]] Specifies the number of input variables.
....oooo [[[[dddd]]]] Specifies the number of output functions.
....ttttyyyyppppeeee [[[[ssss]]]] Sets the logical interpretation of the character
matrix as described below under "Logical
Description of a PLA". This keyword must come
before any product terms. [s] is one of f, r,
fd, fr, dr, or fdr.
....pppphhhhaaaasssseeee [[[[ssss]]]] [s] is a string of as many 0's or 1's as there
are output functions. It specifies which
polarity of each output function should be used
for the minimization (a 1 specifies that the
ON-set of the corresponding output function
should be used, and a 0 specifies that the OFF-
set of the corresponding output function should
be minimized).
....ppppaaaaiiiirrrr [[[[dddd]]]] Specifies the number of pairs of variables which
will be paired together using two-bit decoders.
The rest of the line contains pairs of numbers
which specify the binary variables of the PLA
which will be paired together. The binary
variables are numbered starting with 1. The PLA
will be reshaped so that any unpaired binary
variables occupy the leftmost part of the array,
then the paired multiple-valued columns, and
finally any multiple-valued variables.
Page 1 (printed 3/14/87)
EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555))))
....kkkkiiiissssssss Sets up for a _k_i_s_s-style minimization.
....pppp [[[[dddd]]]] Specifies the number of product terms. The
product terms (one per line) follow immediately
after this keyword. Actually, this line is
ignored, and the ".e", ".end", or the end of the
file indicate the end of the input description.
....eeee ((((....eeeennnndddd)))) Marks the end of the PLA description.
LLLLOOOOGGGGIIIICCCCAAAALLLL DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN OOOOFFFF AAAA PPPPLLLLAAAA
When we speak of the ON-set of a Boolean function, we mean
those minterms which imply the function value is a 1.
Likewise, the OFF-set are those terms which imply the
function is a 0, and the DC-set (don't care set) are those
terms for which the function is unspecified. A function is
completely described by providing its ON-set, OFF-set and
DC-set. Note that all minterms lie in the union of the ON-
set, OFF-set and DC-set, and that the ON-set, OFF-set and
DC-set share no minterms.
The purpose of the _e_s_p_r_e_s_s_o minimization program is to find
a logically equivalent set of product-terms to represent the
ON-set and optionally minterms which lie in the DC-set,
without containing any minterms of the OFF-set.
A Boolean function can be described in one of the following
ways:
1) By providing the ON-set. In this case, _e_s_p_r_e_s_s_o
computes the OFF-set as the complement of the ON-set
and the DC-set is empty. This is indicated with the
keyword ".type f" in the input file, or "-f" on the
command line.
2) By providing the ON-set and DC-set. In this case,
_e_s_p_r_e_s_s_o computes the OFF-set as the complement of the
union of the ON-set and the DC-set. If any minterm
belongs to both the ON-set and DC-set, then it is
considered a don't care and may be removed from the
ON-set during the minimization process. This is
indicated with the keyword ".type fd" in the input
file, or "-fd" on the command line.
3) By providing the ON-set and OFF-set. In this case,
_e_s_p_r_e_s_s_o computes the DC-set as the complement of the
union of the ON-set and the OFF-set. It is an error
for any minterm to belong to both the ON-set and OFF-
set. This error may not be detected during the
minimization, but it can be checked with the subprogram
Page 2 (printed 3/14/87)
EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555))))
"-do check" which will check the consistency of a
function. This is indicated with the keyword ".type
fr" in the input file, or "-fr" on the command line.
4) By providing the ON-set, OFF-set and DC-set. This is
indicated with the keyword ".type fdr" in the input
file, or "-fdr" on the command line.
If at all possible, _e_s_p_r_e_s_s_o should be given the DC-set
(either implicitly or explicitly) in order to improve the
results of the minimization.
A term is represented by a "cube" which can be considered
either a compact representation of an algebraic product term
which implies the function value is a 1, or as a
representation of a row in a PLA which implements the term.
A cube has an input part which corresponds to the input
plane of a PLA, and an output part which corresponds to the
output plane of a PLA (for the multiple-valued case, see
below).
SSSSYYYYMMMMBBBBOOOOLLLLSSSS IIIINNNN TTTTHHHHEEEE PPPPLLLLAAAA MMMMAAAATTTTRRRRIIIIXXXX AAAANNNNDDDD TTTTHHHHEEEEIIIIRRRR IIIINNNNTTTTEEEERRRRPPPPRRRREEEETTTTAAAATTTTIIIIOOOONNNN
Each position in the input plane corresponds to an input
variable where a 0 implies the corresponding input literal
appears complemented in the product term, a 1 implies the
input literal appears uncomplemented in the product term,
and - implies the input literal does not appear in the
product term.
With logical type _f, for each output, a 1 means this product
term belongs to the ON-set, and a 0 or - means this product
term has no meaning for the value of this function. This
logical type corresponds to an actual PLA where only the
ON-set is actually implemented.
With logical type _f_d (the default), for each output, a 1
means this product term belongs to the ON-set, a 0 means
this product term has no meaning for the value of this
function, and a - implies this product term belongs to the
DC-set.
With logical type _f_r, for each output, a 1 means this
product term belongs to the ON-set, a 0 means this product
term belongs to the OFF-set, and a - means this product term
has no meaning for the value of this function.
With logical type _f_d_r, for each output, a 1 means this
product term belongs to the ON-set, a 0 means this product
term belongs to the OFF-set, a - means this product term
belongs to the DC-set, and a ~ implies this product term has
no meaning for the value of this function.
Page 3 (printed 3/14/87)
EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555))))
Note that regardless of the logical type of PLA, a ~ implies
the product term has no meaning for the value of this
function. 2 is allowed as a synonym for -, 4 is allowed for
1, and 3 is allowed for ~. Also, the logical PLA type can
also be specified on the command line.
MMMMUUUULLLLTTTTIIIIPPPPLLLLEEEE----VVVVAAAALLLLUUUUEEEEDDDD FFFFUUUUNNNNCCCCTTTTIIIIOOOONNNNSSSS
Espresso will also minimize multiple-valued Boolean
functions. There can be an arbitrary number of multiple-
valued variables, and each can be of a different size. If
there are also binary-valued variables, they should be given
as the first variables on the line (for ease of
description). Of course, it is always possible to place
them anywhere on the line as a two-valued multiple-valued
variable. The function size is described by the imbedded
option ".mv" rather than ".i" and ".o".
....mmmmvvvv [[[[nnnnuuuummmm____vvvvaaaarrrr]]]] [[[[nnnnuuuummmm____bbbbiiiinnnnaaaarrrryyyy____vvvvaaaarrrr]]]] [[[[ssss1111]]]] .... .... .... [[[[ssssnnnn]]]]
Specifies the number of variables (num_var), the
number of binary variables (num_binary_var), and
the size of each of the multiple-valued
variables (s1 through sn). A multiple-output
binary function with _n_i inputs and _n_o outputs
would be specified as ".mv _n_i+_1 _n_i _n_o." ".mv"
cannot be used with either ".i" or ".o" - use
one or the other to specify the function size.
The binary variables are given as described above. Each of
the multiple-valued variables are given as a bit-vector of 0
and 1 which have their usual meaning for multiple-valued
functions. The last multiple-valued variable (also called
the output) is interpreted as described above for the output
(to split the function into an ON-set, OFF-set and DC-set).
A vertical bar "|" may be used to separate the multiple-
valued fields in the input file.
If the size of the multiple-valued field is less than zero,
than a symbolic field is interpreted from the input file.
The absolute value of the size specifies the maximum number
of unique symbolic labels which are expected in this column.
The symbolic labels are white-space delimited strings of
characters.
To perform a _k_i_s_s-style encoding problem, either the keyword
....kkkkiiiissssssss must be in the file, or the ----kkkkiiiissssssss option must be used
on the command line. Further, the third to last variable on
the input file must be the symbolic "present state", and the
second to last variable must be the "next state". As
always, the last variable is the output. The symbolic "next
state" will be hacked to be actually part of the output.
Page 4 (printed 3/14/87)
EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555))))
EEEEXXXXAAAAMMMMPPPPLLLLEEEE ####1111
A two-bit adder which takes in two 2-bit operands and
produces a 3-bit result can be described completely in
minterms as:
# 2-bit by 2-bit binary adder (with no carry input)
.i 4
.o 3
.type fr
.pair 2 (1 3) (2 4)
.phase 011
00 00 000
00 01 001
00 10 010
00 11 011
01 00 001
01 01 010
01 10 011
01 11 100
10 00 010
10 01 011
10 10 100
10 11 101
11 00 011
11 01 100
11 10 101
11 11 110
.end
The logical format for this input file (i.e., type fr) is
given to indicate that the file contains both the ON-set and
the OFF-set. Note that in this case, the zeros in the
output plane are really specifying "value must be zero"
rather than "no information".
The imbedded option ._p_a_i_r indicates that the first binary-
valued variable should be paired with the third binary-
valued variable, and that the second variable should be
paired with the fourth variable. The function will then be
mapped into an equivalent multiple-valued minimization
problem.
The imbedded option ._p_h_a_s_e indicates that the positive-phase
should be used for the second and third outputs, and that
the negative phase should be used for the first output.
Page 5 (printed 3/14/87)
EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555))))
EEEEXXXXAAAAMMMMPPPPLLLLEEEE ####2222
This example shows a description of a multiple-valued
function with 5 binary variables and 3 multiple-valued
variables (8 variables total) where the multiple-valued
variables have sizes of 4 27 and 10 (note that the last
multiple-valued variable is the "output" and also encodes
the ON-set, DC-set and OFF-set information).
.mv 8 5 4 27 10
0-010|1000|100000000000000000000000000|0010000000
10-10|1000|010000000000000000000000000|1000000000
0-111|1000|001000000000000000000000000|0001000000
0-10-|1000|000100000000000000000000000|0001000000
00000|1000|000010000000000000000000000|1000000000
00010|1000|000001000000000000000000000|0010000000
01001|1000|000000100000000000000000000|0000000010
0101-|1000|000000010000000000000000000|0000000000
0-0-0|1000|000000001000000000000000000|1000000000
10000|1000|000000000100000000000000000|0000000000
11100|1000|000000000010000000000000000|0010000000
10-10|1000|000000000001000000000000000|0000000000
11111|1000|000000000000100000000000000|0010000000
.
.
.
11111|0001|000000000000000000000000001|0000000000
Page 6 (printed 3/14/87)
EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555)))) XXXXEEEENNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((11112222////22228888////88884444)))) EEEESSSSPPPPRRRREEEESSSSSSSSOOOO((((5555))))
EEEEXXXXAAAAMMMMPPPPLLLLEEEE ####3333
This example shows a description of a multiple-valued
function setup for _k_i_s_s-style minimization. There are 5
binary variables, 2 symbolic variables (the present-state
and the next-state of the FSM) and the output (8 variables
total).
.mv 8 5 -10 -10 6
.type fr
.kiss
# This is a translation of IOFSM from OPUS
# inputs are IO1 IO0 INIT SWR MACK
# outputs are WAIT MINIT MRD SACK MWR DLI
# reset logic
--1-- - init0 110000
# wait for INIT to go away
--1-- init0 init0 110000
--0-- init0 init1 110000
# wait for SWR
--00- init1 init1 110000
--01- init1 init2 110001
# Latch address
--0-- init2 init4 110100
# wait for SWR to go away
--01- init4 init4 110100
--00- init4 iowait 000000
# wait for command from MFSM
0000- iowait iowait 000000
1000- iowait init1 110000
01000 iowait read0 101000
11000 iowait write0 100010
01001 iowait rmack 100000
11001 iowait wmack 100000
--01- iowait init2 110001
# wait for MACK to fall (read operation)
--0-0 rmack rmack 100000
--0-1 rmack read0 101000
# wait for MACK to fall (write operation)
--0-0 wmack wmack 100000
--0-1 wmack write0 100010
# perform read operation
--0-- read0 read1 101001
--0-- read1 iowait 000000
# perform write operation
--0-- write0 iowait 000000
.end
Page 7 (printed 3/14/87)